mod tree_node;

use tree_node::TreeNode;
use std::rc::Rc;
use std::cell::RefCell;
use std::collections::HashMap;

struct Solution;

impl Solution {
    pub fn all_possible_fbt(n: i32) -> Vec<Option<Rc<RefCell<TreeNode>>>> {
        if n <= 0 || n % 2 == 0 {
            return vec![];
        }
        if n == 1 {
            let mut vec = vec![];
            let node = Some(Rc::new(RefCell::new(TreeNode::new(0))));
            vec.push(node);
            return vec;
        }

        let mut map: HashMap<i32, Vec<Option<Rc<RefCell<TreeNode>>>>> = HashMap::new();
        Solution::generate(n, &mut map);
        map.remove(&n).unwrap()
    }

    fn generate(n: i32, map: &mut HashMap<i32, Vec<Option<Rc<RefCell<TreeNode>>>>>) {
        if n <= 0 || n % 2 == 0 {
            return;
        }
        if map.contains_key(&n) {
            return;
        }
        if n == 1 {
            let node = Some(Rc::new(RefCell::new(TreeNode::new(0))));
            map.insert(1, vec![node]);
            return;
        }
        let mut left = 1;
        let mut vec = vec![];
        while left < n {
            let right = n - 1 - left;
            Solution::generate(left, map);
            Solution::generate(right, map);
            let left_vec = map.get(&left).unwrap();
            let right_vec = map.get(&right).unwrap();
            for left_node in left_vec {
                for right_node in right_vec {
                    let root = Rc::new(RefCell::new(TreeNode::new(0)));
                    root.borrow_mut().left = left_node.clone();
                    root.borrow_mut().right = right_node.clone();
                    vec.push(Some(root));
                }
            }
            left += 2;
        }
        map.insert(n, vec);
    }
}


fn main() {
    Solution::all_possible_fbt(0);
}
